Compressed sensing, also known as compressive sensing or compressed sampling or sparse sampling is a rapid growing field that has attracted considerable attention in recent years.
The ever increasing amount of data generated by sensing systems such as wireless sensor networks (WSNs) has dramatically emphasized the need for sampling measurement signals at a low rate, i.e. below the Nyquist frequency. Compressive sensing theory states that a signal can be sampled without information loss at a rate close to its information content (Landau rate).
In general, sampling a signal x below the Nyquist frequency, that is at a frequency lower than fNyq=2fmax, where fmax is the highest frequency present in the spectrum, leads to aliasing and therefore impedes signal recovery. Assuming that the signal is sampled at the Nyquist frequency fNyq in a given interval of a real (e.g. of time or space), it can be represented by a vector denoted x of size N in the canonical basis (instants in time, points in space) of this domain.
However, if the representation of x is K-sparse in a given domain (hereinafter called sparse domain), i.e. has at most K nonzero values in a basis spanning this domain, it can be recovered from a number M of linear measurements which is in the order of magnitude of K log N. If we denote y the measurement vector that is the vector constituted of these M linear measurements, it can be expressed as:y=Φx=ΦΨs  (1)where s is the K-sparse representation of x in the sparse domain, Y is the transformation matrix (also called sparsity matrix) of size N×N from the basis spanning the dual domain to the canonical basis, and Φ is the measurement matrix (also called acquisition matrix) of size M×N, with typically M<<N, capturing the reduction of dimensionality.
The signal s can then be recovered from the measurement vector y, the signal estimate ŝ being obtained minimizing the L1-norm:
                              s          ^                =                                                            arg                ⁢                                                                  ⁢                min                                            z                ∈                                  B                  ⁡                                      (                    y                    )                                                                        ⁢                                                          z                                                            l                1                                      ⁢                                                  ⁢            where            ⁢                                                  ⁢                          B              ⁡                              (                y                )                                              =                      {                          z              |                                                                                                                                      ΦΨ                        ⁢                                                                                                  ⁢                        z                                            -                      y                                                                                                l                    2                                                  ≤                ɛ                                      }                                              (        2        )            where, l1 and l2 denote respectively the L1-norm and the L2-norm, B(y) ensures that ŝ is consistent with the measurement vector y and ε is a tolerance parameter dependent upon the noise.
Several reconstruction algorithms have been proposed in the literature, e.g. the basic pursuit algorithm (BP), the orthogonal matching pursuit algorithm (OMP) and the tree-based OMP (TOMP).
A comprehensive introduction to compressive sensing can be found in Chap. I of the book entitled “Compressive sensing: theory and its applications” by Y. C. Eldar and G. Kutyniok, Cambridge University Press, 2012.
A first example of compressive sensing method is non-uniform sampling (NUS).
We assume in the following that the signal to be sampled is K-sparse in the frequency domain.
Non-uniform sampling allows a sample rate close to the optimal information rate (i.e. the Landau rate) to be approached without complicated analog processing. In a nutshell, a NUS sampler samples the input signal at irregularly distributed instants by taking only a subset of the samples of a Nyquist converter. Assuming an acquisition window of length Tacq, the number of samples acquired by the NUS is equal to M<N=fNyqTacq, where M samples are chosen at random among the N samples of the Nyquist converter.
As shown on FIG. 1, a NUS sampler can be implemented by a sample-and-hold stage followed by an ADC operating at a sampling rate corresponding to the shortest sampling period used by the NUS.
Using the formalism of expression (1) the non-uniform sampling can be expressed as:y=RTINF1s  (3)where the transformation matrix is here Ψ=F−1, i.e. the inverse discrete Fourier transform (DFT), IN is the matrix identity of size N×N, with N=fNyqTacq, and RT is a selection matrix of size M×N representing a random selection of M columns among N of the identity matrix. Each row of RT has an element equal to 1 and all other elements equal to 0, the M column indicia of the elements equaling to 1 being chosen at random among {1, . . . , N}. The measurement matrix is therefore simply Φ=RTIN.
The non-uniform sampling method is a simple compressive method but has several shortcomings.
First, in case the signal input to the NUS sampler is wideband, the ADC still needs to capture a snapshot of this wideband signal with frequencies possibly reaching up to the highest frequency present in the spectrum.
Second, although the NUS sampler operates at a sub-Nyquist rate, a clock at the Nyquist rate is required to synchronize the samples.
Third, a NUS sampler is highly sensitive to timing jitter. If the input signal varies rapidly, a small error in the sampling time may lead to an erroneous sample value.
A second example of compressive sensing method is random-modulation pre-integration (RMPI). According to this scheme, the signal is mixed in parallel channels with a plurality of pseudo-random binary sequences (PRBS) at the Nyquist rate, the output results being integrated and sampled at a low rate. The idea behind RMPI is that it is much easier to mix a wideband signal at the Nyquist rate than to accurately sample it at this rate.
More recently, it has been proposed in patent U.S. Pat. No. 8,836,557 to achieve compressed sensing of a signal by exploiting its sparsity in a Gabor frame representation. More specifically, the signal is mixed in a plurality of channels operating in parallel with modulating waveforms belonging to a Gabor frame and the modulation products are integrated over a finite time interval. The modulating waveforms are designed such that the mixing operation produces weighted superposition of various subs-sections of the signal related to different sub-intervals of the finite time interval. The integration results provide sample values that represent the signal and enable its reconstruction.
However, this method is not optimal for a multiband signal inasmuch as it does not exploit the structure of the signal spectrum. In addition, the pseudo-random binary sequence needs to be run at a high rate and therefore leads to a high power consumption.
The purpose of the present invention is therefore to propose a compressed sensing method which does not present the disadvantages of the prior art, in particular which enables sampling of a sparse multi-band signal at a very low rate, close to the information rate.